from typing import List


class Solution:
    """
    方法：贪心算法
    Args:
        s: 输入字符串
    Returns:
        List[int]: 每个分区的长度列表
    Time: O(n), n为字符串长度
    Space: O(1), 最多存储26个字母的最后出现位置
    """
    def partitionLabels(self, s: str) -> List[int]:
        last = {c : i for i, c in enumerate(s)} # 每个字母最后出现的下标
        ans = []
        start = end = 0
        for i, c in enumerate(s):
            # 更新当前区间右端点的最大值
            end = max(end, last[c])
            if end == i:  # 当前区间合并完毕
                ans.append(end - start + 1)
                start = i + 1  # 下一个区间的左端点
        return ans
